{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Events That Can Be Attended"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxEvents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最多可以参加的会议数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组&nbsp;<code>events</code>，其中&nbsp;<code>events[i] = [startDay<sub>i</sub>, endDay<sub>i</sub>]</code>&nbsp;，表示会议&nbsp;<code>i</code>&nbsp;开始于&nbsp;<code>startDay<sub>i</sub></code>&nbsp;，结束于&nbsp;<code>endDay<sub>i</sub></code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以在满足&nbsp;<code>startDay<sub>i</sub>&nbsp;&lt;= d &lt;= endDay<sub>i</sub></code><sub>&nbsp;</sub>中的任意一天&nbsp;<code>d</code>&nbsp;参加会议&nbsp;<code>i</code>&nbsp;。注意，一天只能参加一个会议。</p>\n",
    "\n",
    "<p>请你返回你可以参加的&nbsp;<strong>最大&nbsp;</strong>会议数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/16/e1.png\" style=\"height: 267px; width: 400px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>events = [[1,2],[2,3],[3,4]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>你可以参加所有的三个会议。\n",
    "安排会议的一种方案如上图。\n",
    "第 1 天参加第一个会议。\n",
    "第 2 天参加第二个会议。\n",
    "第 3 天参加第三个会议。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>events= [[1,2],[2,3],[3,4],[1,2]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong>​​​​​​</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= events.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>events[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= startDay<sub>i</sub>&nbsp;&lt;= endDay<sub>i</sub>&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-events-that-can-be-attended](https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-events-that-can-be-attended](https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,3],[3,4]]', '[[1,2],[2,3],[3,4],[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(reverse=True)\n",
    "        ans=0\n",
    "        que=[]\n",
    "        for i in range(1,100001):\n",
    "            while events and events[-1][0]==i:\n",
    "                heappush(que,events.pop()[-1])\n",
    "            while que:\n",
    "                # cur=que.pop()\n",
    "                cur=heappop(que)\n",
    "                if i<=cur:\n",
    "                    ans+=1\n",
    "                    break\n",
    "            if not que and not events:break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(reverse = True)\n",
    "        h = []\n",
    "        ans = 0\n",
    "        for i in range(1,100001):\n",
    "            while events and events[-1][0] == i:\n",
    "                heappush(h,events.pop()[1])\n",
    "            while h:\n",
    "                cur = heappop(h)\n",
    "                if cur >= i:\n",
    "                    ans += 1\n",
    "                    break\n",
    "            if not events and not h:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(reverse=True)\n",
    "        pq = []\n",
    "        res = 0\n",
    "        for i in range(1,100001):\n",
    "            while events and events[-1][0]==i:\n",
    "                heapq.heappush(pq,events.pop()[1])\n",
    "            while pq:\n",
    "                end = heappop(pq)\n",
    "                if end>=i:\n",
    "                    res+=1\n",
    "                    break\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "class Solution:\n",
    "    MAX_NUMBER = 10 ** 5 + 1\n",
    "    def maxEvents01(self, events: List[List[int]]) -> int:\n",
    "        events_by_start_day = [list() for _ in range(self.MAX_NUMBER)]\n",
    "        for i, e in enumerate(events):\n",
    "            events_by_start_day[e[0]].append(i)\n",
    "        available_events = list()\n",
    "        cnt = 0\n",
    "        for cur_day in range(1, self.MAX_NUMBER):\n",
    "            for seq in events_by_start_day[cur_day]:\n",
    "                heappush(available_events, events[seq][1])\n",
    "            \n",
    "            while available_events:\n",
    "                k = heappop(available_events)\n",
    "                if k < cur_day:\n",
    "                    continue\n",
    "                cnt += 1\n",
    "                break\n",
    "        return cnt\n",
    "    \n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        visited = {}\n",
    "        for s, e in events:\n",
    "            while s <= e and s in visited:\n",
    "                s += 1\n",
    "            if s <= e:\n",
    "                visited[s] = 1\n",
    "        return len(visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda x:x[1])\n",
    "        visited = set()\n",
    "        for s,e in events:\n",
    "            for day in range(s,e+1):\n",
    "                if day not in visited:\n",
    "                    visited.add(day)\n",
    "                    break\n",
    "        return len(visited)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self,events):\n",
    "        if len(events)<=1:\n",
    "            return len(events)\n",
    "        events.sort(key=lambda x:x[1])\n",
    "        visited = set()\n",
    "        for s,t in events:\n",
    "            for day in range(s,t+1):\n",
    "                if day not in visited:\n",
    "                    visited.add(day)\n",
    "                    break\n",
    "        return len(visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        # 贪心算法，使用优先队列、堆、哈希表。\n",
    "        # 将每天能参加的所有活动，按照结束时间从小到大，整理成一个优先队列，每天将队头取出。\n",
    "        # 整体的贪心策略就是尽可能安排这一天开一个结束日期最早的会\n",
    "        \n",
    "        # if not events:\n",
    "        #     return 0\n",
    "        # events = sorted(events, key=lambda x: x[1])\n",
    "        # plain = set()\n",
    "        # for event in events:\n",
    "        #      for i in range(event[0], event[1]+1):\n",
    "        #         if i not in plain:\n",
    "        #             plain.add(i)\n",
    "        #             break\n",
    "        # return len(plain)\n",
    "\n",
    "        ht, ans, maxEnd = [[] for i in range(100001)], 0, 0\n",
    "        for e in events:\n",
    "            ht[e[0]].append(e[1])\n",
    "            maxEnd = max(maxEnd, e[1])\n",
    "        # q : List[int] - 所有当前可以参加的活动的结束日期\n",
    "        q = []\n",
    "        for i in range(1, maxEnd+1):\n",
    "            # 在第i天，那些于第i天开始的活动可以被加入q中\n",
    "            for e in ht[i]:\n",
    "                heapq.heappush(q, e)\n",
    "            # 选取一个结束时间最早的活动\n",
    "            if len(q) != 0:\n",
    "                heapq.heappop(q)\n",
    "                ans += 1\n",
    "                # 把所有结束时间<=i（也就是过了今天就不能再参加）的活动从q中移除\n",
    "                while len(q):\n",
    "                    e = heapq.heappop(q)\n",
    "                    if e > i:\n",
    "                        heapq.heappush(q, e)\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        '''\n",
    "        heapq.heapify(events)\n",
    "        n = day = 0\n",
    "        while events: # make sure taking the upcoming, shorestest-lasting event available from 'day'\n",
    "            [s, t] = heapq.heappop(events) \n",
    "            # attend this event on the s-th day \n",
    "            day = s + 1 # need to increment 'day'\n",
    "            n += 1 # event attended + 1\n",
    "            while events and events[0][0] < day: # update other events' available times, to start no earlier than 'day'\n",
    "                [c, d] = heapq.heappop(events)\n",
    "                if day <= d:\n",
    "                    heapq.heappush(events, [day, d])\n",
    "        return n\n",
    "        '''\n",
    "        ht = [[] for i in range(100001)]\n",
    "        ans = 0 \n",
    "        maxEnd = 0\n",
    "        for event in events:\n",
    "            ht[event[0]].append(event[1])\n",
    "            maxEnd = max(maxEnd, event[1])\n",
    "        queue = []\n",
    "        for i in range(1, maxEnd+1):\n",
    "            for end_time in ht[i]:\n",
    "                heapq.heappush(queue, end_time)\n",
    "            if queue:\n",
    "                heapq.heappop(queue)\n",
    "                ans += 1\n",
    "                while queue:\n",
    "                    end_time = queue[0]\n",
    "                    if end_time <= i:\n",
    "                        end_time = heapq.heappop(queue)\n",
    "                    else:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        start = events[0][0]\n",
    "        end = events[0][1]\n",
    "        for event in events:\n",
    "            start = min(start,event[0])\n",
    "            end = max(end,event[1])\n",
    "        day = start\n",
    "        events.sort(key = lambda x:(x[0],x[1]))\n",
    "        cur = []\n",
    "        count = 0\n",
    "        print(events)\n",
    "\n",
    "        while day <= end:\n",
    "            while len(events) > 0 and events[0][0] <= day:\n",
    "                enter = events.pop(0)\n",
    "                enter = (enter[1],enter)\n",
    "                heappush(cur,enter)\n",
    "            while len(cur)>0 and cur[0][1][1] < day:\n",
    "                heappop(cur)\n",
    "            if len(cur) > 0:\n",
    "                heappop(cur)\n",
    "                count = count + 1\n",
    "            day += 1\n",
    "        return count\n",
    "        #     minheap = []\n",
    "        #     heapq.heappush(heap, item)\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        #贪心 结束的早的先开\n",
    "        #优先队列就是堆 大顶堆和小顶堆 每次能够弹出一个最值 时间复杂度较小 heapq\n",
    "        #核心操作是 heappush heappop 入堆 出堆\n",
    "        #如果本身list是有元素的 需要先用函数将list改为堆 \n",
    "        #要么就直接建立一个空的list 然后一个一个压进去 \n",
    "\n",
    "        #遍历所有的时间点 模拟了会议的开始和结束 并且总是贪心的选择最早结束的会议进行参加\n",
    "        # [[30, 31], [27, 27], [25, 29], [23, 25], [20, 21], [17, 20], [17, 17], [13, 14], [13, 14], [12, 12], [12, 12], \n",
    "        #     30         27         25          23            20         18           17       14       13      12\n",
    "        # [10, 14], [9, 11], [8, 10], [7, 7], [7, 7], [6, 10], [6, 9], [4, 8], [4, 6]]\n",
    "        #     11         10       9                7       8        6        5        4\n",
    "\n",
    "        events.sort(key=lambda x : (x[0], x[1]), reverse=True)\n",
    "        print(events)\n",
    "        print(len(events))\n",
    "        heap = []\n",
    "        res = 0\n",
    "        for i in range(1, 100001):\n",
    "            while events and events[-1][0] <= i:\n",
    "                tmp = events.pop()\n",
    "                heappush(heap, tmp[1])\n",
    "            # if i == 8:\n",
    "            #     print(heap)\n",
    "            if heap:\n",
    "                x = heappop(heap)\n",
    "                \n",
    "                if i <= x:\n",
    "                    # print(x, i)\n",
    "                    \n",
    "                    res += 1\n",
    "                    if heap:\n",
    "                        x = heappop(heap)\n",
    "                        while  heap and x <= i:\n",
    "                            x = heappop(heap)\n",
    "                        if x > i:\n",
    "                            heappush(heap, x)\n",
    "\n",
    "            if not events and not heap:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda x:(-x[0],x[1])) #排序的作用是从后往前判断开始时间，并弹出它\n",
    "        h = [] #优先队列，也可以说是小顶堆\n",
    "        ans = 0\n",
    "        for i in range(1,100001):  #直接用数据范围（当然也可以取events结束时间的最大值，还要再写循环不够简练）\n",
    "            while events and events[-1][0]==i:\n",
    "                heapq.heappush(h,events.pop()[1])\n",
    "            while h:\n",
    "                cur=heapq.heappop(h)\n",
    "                if cur>=i:\n",
    "                    ans+=1\n",
    "                    break\n",
    "            if not events and not h:\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        if events == []:\n",
    "            return 0\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        count = 1\n",
    "        dct = {}\n",
    "        start = events[0][0]\n",
    "        dct[start] = 1\n",
    "        for event in events[1:]:\n",
    "            for i in range(event[0], event[1]+1):\n",
    "                if dct.get(i, 0) == 0:\n",
    "                    count += 1\n",
    "                    dct[i] = 1\n",
    "                    break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self,events):\n",
    "        events.sort(key=lambda x:x[1])\n",
    "        visited = {}\n",
    "        for s,e in events:\n",
    "            for day in range(s,e+1):\n",
    "                if day not in visited:\n",
    "                    visited[day]=1\n",
    "                    break\n",
    "        return len(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        end = list()\n",
    "        events = sorted(events,reverse=True)\n",
    "        print(events)\n",
    "        for i in range(1,10 ** 5 + 1,1):\n",
    "            while events and events[-1][0] == i:\n",
    "                heapq.heappush(end, events.pop()[1])\n",
    "            while end and end[0] < i:\n",
    "                heapq.heappop(end)\n",
    "            if end:\n",
    "                heapq.heappop(end)\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda x: -x[0])\n",
    "        h = [] #优先队列，也可以说是小顶堆\n",
    "        ans = 0\n",
    "        for i in range(1,100001):  #直接用数据范围（当然也可以取events结束时间的最大值，还要再写循环不够简练）\n",
    "            while events and events[-1][0]==i: #排序的作用\n",
    "                heapq.heappush(h,events.pop()[1]) #弹出\n",
    "            while h:\n",
    "                cur = heapq.heappop(h)\n",
    "                if cur>=i:\n",
    "                    ans+=1 #一天只能参加一次\n",
    "                    break\n",
    "            if not events and not h:break #既没有新源，也没有旧源，直接结束\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        import heapq\n",
    "        # 按会议起始时间降序排序\n",
    "        events.sort(key=lambda x: -x[0])\n",
    "        h = [] # 优先队列\n",
    "        ans = 0\n",
    "        # 输入范围为1~10^5\n",
    "        for i in range(1,100001):\n",
    "            # 如果当前时刻有会议刚好开始\n",
    "            # 将其加入堆中，并移除出events\n",
    "            while events and events[-1][0]==i: \n",
    "                heapq.heappush(h, events.pop()[1])\n",
    "            while h:\n",
    "                # 注意，cur可能是已截止的会议\n",
    "                cur = heapq.heappop(h)\n",
    "                # 如果找到一个可参加的会议，则参加\n",
    "                if cur >= i:\n",
    "                    ans += 1\n",
    "                    break\n",
    "            # 所有会议都被考虑完毕，结束\n",
    "            if not events and not h:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "    \n",
    "        events = sorted(events, key =lambda x : x[0])\n",
    "        ans = 0\n",
    "        small_headp = []\n",
    "        import heapq\n",
    "        i ,day , n = 0 ,events[0][0], len(events)\n",
    "        while True:\n",
    "            while i<n and events[i][0] <= day :# 第i天开始的会议都加入small_headp\n",
    "                heapq.heappush(small_headp , events[i][1])\n",
    "                i +=1\n",
    "            while len(small_headp) >0 and small_headp[0] < day: #day那天及之前结束的会议都拿出来\n",
    "                heapq.heappop(small_headp)\n",
    "            if len(small_headp) >0:\n",
    "                ans += 1\n",
    "                heapq.heappop(small_headp)\n",
    "            day +=1\n",
    "            if i ==n and len(small_headp) == 0: \n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key = lambda x: (x[0], x[1]))\n",
    "        min_day = float('inf')\n",
    "        max_day = -float('inf')\n",
    "        for event in events:\n",
    "            min_day = min(min_day, event[0])\n",
    "            max_day = max(max_day, event[1])\n",
    "\n",
    "        result = 0\n",
    "        currEvent = 0\n",
    "        n = len(events)\n",
    "        q = []\n",
    "        for day in range(min_day, max_day + 1):\n",
    "            while currEvent < n and events[currEvent][0] <= day:\n",
    "                heapq.heappush(q, events[currEvent][1])\n",
    "                currEvent += 1\n",
    "            while q and day > q[0]:\n",
    "                heapq.heappop(q)\n",
    "            if q:\n",
    "                heapq.heappop(q)\n",
    "                result += 1\n",
    "        return result\n",
    "        # events.sort(key=lambda x:(x[0], x[1]))\n",
    "        # q = []\n",
    "        # time = 0\n",
    "        # result = 0\n",
    "        # n = len(events)\n",
    "        # i = 0\n",
    "        # while(i < n or q):\n",
    "        #     time += 1\n",
    "        #     while q and time > q[0]:\n",
    "        #         heapq.heappop(q)\n",
    "        #     while i < n and events[i][0] == time:\n",
    "        #         heapq.heappush(q, events[i][1])\n",
    "        #         i += 1\n",
    "        #     if q:\n",
    "        #         result += 1\n",
    "        #         heapq.heappop(q)\n",
    "        # return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        # events.sort(key = lambda x: (x[0], x[1]))\n",
    "        # min_day = float('inf')\n",
    "        # max_day = -float('inf')\n",
    "        # for event in events:\n",
    "        #     min_day = min(min_day, event[0])\n",
    "        #     max_day = max(max_day, event[1])\n",
    "\n",
    "        # result = 0\n",
    "        # currEvent = 0\n",
    "        # n = len(events)\n",
    "        # q = []\n",
    "        # for day in range(min_day, max_day + 1):\n",
    "        #     while currEvent < n and events[currEvent][0] <= day:\n",
    "        #         heapq.heappush(q, events[currEvent][1])\n",
    "        #         currEvent += 1\n",
    "        #     while q and day > q[0]:\n",
    "        #         heapq.heappop(q)\n",
    "        #     if q:\n",
    "        #         heapq.heappop(q)\n",
    "        #         result += 1\n",
    "        # return result\n",
    "        events.sort(key=lambda x:(x[0], x[1]))\n",
    "        q = []\n",
    "        time = 0\n",
    "        result = 0\n",
    "        n = len(events)\n",
    "        i = 0\n",
    "        while(i < n or q):\n",
    "            time += 1\n",
    "            while q and time > q[0]:\n",
    "                heapq.heappop(q)\n",
    "            while i < n and events[i][0] == time:\n",
    "                heapq.heappush(q, events[i][1])\n",
    "                i += 1\n",
    "            if q:\n",
    "                result += 1\n",
    "                heapq.heappop(q)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        ends = max(e[1] for e in events)\n",
    "        events.append((ends+1, -1))\n",
    "        events.sort(key=lambda x: (x[0], -x[1]), reverse=True)\n",
    "        \n",
    "        pq = []\n",
    "        ans = 0\n",
    "        t = 0\n",
    "        while t <= ends:\n",
    "            while pq and pq[0] < t: #pop finished events\n",
    "                heappop(pq)\n",
    "            while events and events[-1][0] <= t: #push started events\n",
    "                heappush(pq, events.pop()[1])\n",
    "            \n",
    "            if pq:\n",
    "                heappop(pq)\n",
    "                ans += 1\n",
    "\n",
    "            if pq:\n",
    "                t += 1\n",
    "            elif events:\n",
    "                t = events[-1][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heapify, heappush, heappop\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        # Create a heap: (start date, end date)\n",
    "        start_end_map = {}\n",
    "        for s, e in events:\n",
    "            if s in start_end_map:\n",
    "                start_end_map[s].append(e)\n",
    "            else:\n",
    "                start_end_map[s] = [e]\n",
    "\n",
    "        # Iterate start date from 1 to n\n",
    "        ct = 0\n",
    "        hp = []\n",
    "        n = max(e for s, e in events)\n",
    "        for s in range(1, n+1):\n",
    "            # Remove events that cannot be done\n",
    "            while hp and hp[0] < s:\n",
    "                heappop(hp)\n",
    "            # Add current start point\n",
    "            if s in start_end_map:\n",
    "                for e in start_end_map[s]:\n",
    "                    heappush(hp, e)\n",
    "            # pop the heap top\n",
    "            if len(hp) > 0:\n",
    "                heappop(hp)\n",
    "                ct += 1\n",
    "        return ct\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        # 难题 容易想错\n",
    "        # events= [[1,5],[1,5],[1,5],[2,3],[2,3]]\n",
    "        # events.sort( key = lambda x : ( x[1], x[0] ) ) # 早结束的 不对\n",
    "        # events.sort()\n",
    "        # ans = 0\n",
    "        # start = 0\n",
    "        # for event in events:\n",
    "        #     if event[1] >= start:\n",
    "        #         start = max(start,event[0])+1\n",
    "        #         ans += 1\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        # 哈希+ 小根堆\n",
    "        d = defaultdict(list)\n",
    "        for i,val in enumerate(events):\n",
    "            d[val[0]].append(val[1])\n",
    "        h = [] #优先队列，也可以说是小顶堆\n",
    "        ans = 0\n",
    "        for i in range(1,100001):\n",
    "            \n",
    "            for end in d[i]:  \n",
    "                heapq.heappush(h,end) \n",
    "            del d[i] #优化字典\n",
    "            # print(h)\n",
    "            while h:\n",
    "                cur = heapq.heappop(h) #结束时间比当前开始时间早的都弹出了，\n",
    "                if cur>=i: #一旦找到一个符合条件的\n",
    "                    ans+=1 \n",
    "                    break #一天只能参加一次\n",
    "            if not d and not h:break #既没有新源d，也没有旧源h，直接结束，优化\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        h=[]\n",
    "        events.sort()\n",
    "        t=events[0][0]\n",
    "        ans=0\n",
    "        for i in events:\n",
    "            while h and t<i[0]:\n",
    "                x=heapq.heappop(h)\n",
    "                if x<t:\n",
    "                    continue\n",
    "                ans+=1\n",
    "                t+=1\n",
    "            t=max(i[0],t)\n",
    "            heapq.heappush(h,i[1])\n",
    "        while h:\n",
    "            x=heapq.heappop(h)\n",
    "            if x<t:\n",
    "                continue\n",
    "            ans+=1\n",
    "            t+=1\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        heap=[]\n",
    "        T=100010\n",
    "        j=0\n",
    "        n=len(events)\n",
    "        res=0\n",
    "        # 枚举每一时刻\n",
    "        for i in range(1,T):\n",
    "            # 删掉过期会议\n",
    "            while heap and heap[0]<i:heappop(heap)\n",
    "            # 加入可选会议\n",
    "            while j<n and events[j][0]==i:\n",
    "                heappush(heap,events[j][1])\n",
    "                j+=1\n",
    "            # 参加最先结束的会议\n",
    "            if heap:\n",
    "                heappop(heap)\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "\n",
    "        events.sort()\n",
    "\n",
    "        from heapq import heappush,heappop\n",
    "        heap=[]\n",
    "        day,res=1,0\n",
    "        i=0\n",
    "        while i<len(events) or heap:\n",
    "            while i<len(events) and events[i][0]==day: \n",
    "                heappush(heap, [events[i][1],events[i][0]])\n",
    "                i+=1\n",
    "            while heap:\n",
    "                p=heappop(heap)\n",
    "                if p[0]>=day:  \n",
    "                    res+=1\n",
    "                    break\n",
    "            day+=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5 + 2\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        events.sort()\n",
    "        n = len(events)\n",
    "        ind = 0\n",
    "        state = []\n",
    "        # 2 * logN\n",
    "        # remove add, 2 * logN\n",
    "        res = 0\n",
    "        for i in range(N):\n",
    "            while ind < n and events[ind][0] <= i:\n",
    "                heapq.heappush(state, events[ind][1])\n",
    "                ind += 1\n",
    "            while state and state[0] < i:\n",
    "                heapq.heappop(state)\n",
    "            if state:\n",
    "                res += 1\n",
    "                heapq.heappop(state)\n",
    "        return res\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        d = dict()\n",
    "        maxlen = 0\n",
    "        for i in range(len(events)):\n",
    "            maxlen = max(maxlen, max(events[i]))\n",
    "            if events[i][0] in d:\n",
    "                d[events[i][0]].append(i)\n",
    "            else:\n",
    "                d[events[i][0]] = [i]\n",
    "        \n",
    "        ans = 0\n",
    "        q = []\n",
    "        for i in range(1, maxlen + 1):\n",
    "            if i in d:\n",
    "                for j in d[i]:\n",
    "                    if events[j][1] >= i:\n",
    "                        heappush(q, events[j][1])\n",
    "            while q and q[0] < i:\n",
    "                heappop(q) \n",
    "            if len(q) > 0:\n",
    "                ans += 1\n",
    "                heappop(q)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        start = []\n",
    "        end = []\n",
    "\n",
    "        for s,e in events:\n",
    "            heapq.heappush( end, ( s,e ) )\n",
    "        now = 1\n",
    "        ans = 0\n",
    "        while start or end:\n",
    "            while end and  end[0][0] <= now:\n",
    "                s,e = heapq.heappop(end)\n",
    "                heapq.heappush(start, (e,s ))\n",
    "\n",
    "            while start and start[0][0] < now:\n",
    "                _ = heapq.heappop(start)\n",
    "            if start:\n",
    "                e, s = heapq.heappop(start)\n",
    "                ans += 1\n",
    "            now += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        MAX=10**5+1\n",
    "        edge=[[] for _ in range(MAX)]\n",
    "        n=len(events)\n",
    "        for i in range(n):\n",
    "            edge[events[i][0]].append(i)\n",
    "        heap=[]\n",
    "        ret=0\n",
    "        for i in range(1,MAX):\n",
    "            for j in edge[i]:\n",
    "                heapq.heappush(heap,events[j][1])\n",
    "            while heap and heap[0]<i:\n",
    "                heapq.heappop(heap)\n",
    "            if heap:\n",
    "                ret+=1\n",
    "                heapq.heappop(heap)\n",
    "        return ret\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        eventsArr = [[] for _ in range(100001)]\n",
    "        # print(events)\n",
    "        for i in range(len(events)):\n",
    "            eventsArr[events[i][0]].append(i)\n",
    "        # print(eventsArr)\n",
    "        heap = []\n",
    "        res = 0\n",
    "        for i in range(100001):\n",
    "            for idx in eventsArr[i]:\n",
    "                heapq.heappush(heap,events[idx][1])\n",
    "            \n",
    "            while heap and heap[0] < i:\n",
    "                heapq.heappop(heap)\n",
    "            \n",
    "            if heap:\n",
    "                res += 1\n",
    "                heapq.heappop(heap)\n",
    "                    \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        heap, ans, n = [], set(), len(events)\n",
    "        events.sort()\n",
    "        end = max(event[1] for event in events)\n",
    "        i = 0\n",
    "        for d in range(1, end + 1):\n",
    "            while heap and heap[0][0] < d:\n",
    "                heapq.heappop(heap)\n",
    "            while i < n and events[i][0] <= d:\n",
    "                heapq.heappush(heap, (events[i][1], i))\n",
    "                i += 1\n",
    "            if heap:\n",
    "                ans.add(heapq.heappop(heap)[1])\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        heap, ans, n = [], set(), len(events)\n",
    "        events.sort()\n",
    "        # end是最后一个有event的日子\n",
    "        end = max(event[1] for event in events)\n",
    "        i = 0\n",
    "        # 遍历整个时间区间，最优的方案肯定是先参加较早结束的event\n",
    "        for d in range(1, end + 1):\n",
    "            # 将当前天已经结束的event全部弹出\n",
    "            while heap and heap[0][0] < d:\n",
    "                heapq.heappop(heap)\n",
    "            # 将当前天开始的event全部加入\n",
    "            while i < n and events[i][0] <= d:\n",
    "                heapq.heappush(heap, (events[i][1], i))\n",
    "                i += 1\n",
    "            # 如果今天还有event，就去参加一个，因为这个已经参加了，后续可以不用再考虑它，可以直接弹出\n",
    "            if heap:\n",
    "                ans.add(heapq.heappop(heap)[1])\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        new_events = sorted(events, key=lambda x: (x[1], x[0]))\n",
    "\n",
    "        max_day = new_events[-1][1]\n",
    "        tmp_arr = [[] for _ in range(max_day + 1)]\n",
    "\n",
    "        for i in range(len(events)):\n",
    "            tmp_arr[events[i][0]].append(i)\n",
    "\n",
    "        m_queue = []\n",
    "        count = 0\n",
    "\n",
    "        for i in range(1, max_day + 1):\n",
    "            for j in tmp_arr[i]:\n",
    "                heapq.heappush(m_queue, events[j][1])\n",
    "\n",
    "            while len(m_queue) > 0 and m_queue[0] < i:\n",
    "                heapq.heappop(m_queue)\n",
    "\n",
    "            if len(m_queue) > 0:\n",
    "                heapq.heappop(m_queue)\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        #events=[[1,1],[2,2],[3,4],[1,4],[4,4]]\n",
    "        start=sorted(enumerate(events),key=lambda x:x[1][0])  \n",
    "\n",
    "        t=1\n",
    "        i,j=0,0\n",
    "        L=len(events)\n",
    "        r=0\n",
    "\n",
    "        from queue import PriorityQueue as PQ\n",
    "        q=PQ()\n",
    "\n",
    "        while i<L or (not q.empty()):\n",
    "            while i<L and t>=start[i][1][0]:   #已开始的会议\n",
    "                midx=start[i][0]\n",
    "                q.put((events[midx][1],midx))\n",
    "                i+=1\n",
    "\n",
    "            if not q.empty(): \n",
    "                p=q.get()\n",
    "                flag=0\n",
    "                while events[p[1]][1]<t:       #已结束的会议，都pop\n",
    "                    if not q.empty():\n",
    "                        p=q.get()\n",
    "                    else:\n",
    "                        flag=1\n",
    "                        break\n",
    "                if not flag:                   #如果有没结束的会议\n",
    "                    #print(p[1],events[p[1]])\n",
    "                    r+=1\n",
    "            t+=1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        if len(events) == 0: return 0\n",
    "        min_s = events[0][0]\n",
    "        max_e = events[0][1]\n",
    "        e_hq = []\n",
    "        s_hq = []\n",
    "        counter = itertools.count()\n",
    "        for event in events:\n",
    "            min_s = min(event[0], min_s)\n",
    "            max_e = max(event[1], max_e)\n",
    "            count = next(counter)\n",
    "            heapq.heappush(s_hq, [event[0], count, event])\n",
    "        cnt = 0\n",
    "        for i in range(min_s, max_e+1):\n",
    "            while len(s_hq) > 0 and s_hq[0][0] == i: \n",
    "                event = heapq.heappop(s_hq)[2]\n",
    "                heapq.heappush(e_hq, [event[1], next(counter), event])\n",
    "            while len(e_hq) > 0 and (i < e_hq[0][2][0] or i > e_hq[0][2][1]):\n",
    "                heapq.heappop(e_hq)\n",
    "            if len(e_hq) > 0 and i >= e_hq[0][2][0] and i <= e_hq[0][2][1]: \n",
    "                heapq.heappop(e_hq)\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key = lambda x:(x[1], x[0]))\n",
    "        arranged = set()\n",
    "        last = events[0][0]\n",
    "        for index in range(len(events)):\n",
    "            xs, xe = events[index]\n",
    "            if index>0 and xs>=events[index-1][0]:\n",
    "                xs=max(xs, last)\n",
    "            for i in range(xs, xe+1):\n",
    "                if i in arranged:\n",
    "                    continue\n",
    "                else:\n",
    "                    arranged.add(i)\n",
    "                    last = i\n",
    "                    break\n",
    "        return len(arranged)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self,events):\n",
    "        import bisect\n",
    "        data, b, e = {}, 100001, 0\n",
    "        for x, y in events:\n",
    "            if x in data: data[x].append(y)\n",
    "            else: data[x] = [y]\n",
    "            b, e = min(b, x), max(e, y)\n",
    "        meet, res = [], 0\n",
    "        for i in range(b, e+1):\n",
    "            while meet and meet[0]<i: meet.pop(0)\n",
    "            if i in data:\n",
    "                for j in data[i]:\n",
    "                    bisect.insort(meet, j)\n",
    "            if len(meet)>0:\n",
    "                res += 1\n",
    "                meet.pop(0)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        temp_arr = [[] for _ in range(10 ** 5 + 1)]\n",
    "        for index, event in enumerate(events):\n",
    "            temp_arr[event[0]].append(index)\n",
    "        \n",
    "        min_queue = []\n",
    "        res = 0\n",
    "        for i in range(1, 10 ** 5 + 1):\n",
    "            for index in temp_arr[i]:\n",
    "                heapq.heappush(min_queue, (events[index][1], events[index][0]))\n",
    "            \n",
    "            while min_queue and min_queue[0][0]  < i:\n",
    "                heapq.heappop(min_queue)\n",
    "            \n",
    "            if min_queue:\n",
    "                res += 1\n",
    "                heapq.heappop(min_queue)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        max_day = 0\n",
    "        import collections\n",
    "        import heapq\n",
    "        start_map = collections.defaultdict(list)\n",
    "        for event in events:\n",
    "            start_map[event[0]].append(event[1])\n",
    "            max_day = max(max_day, event[1])\n",
    "        cnt = 0\n",
    "        heap = []\n",
    "        for i in range(1, max_day + 1):\n",
    "            while heap and heap[0] < i:\n",
    "                heapq.heappop(heap)\n",
    "            if i in start_map:\n",
    "                while start_map[i]:\n",
    "                    heapq.heappush(heap, start_map[i].pop())\n",
    "            if heap:\n",
    "                cnt += 1\n",
    "                heapq.heappop(heap)\n",
    "        return cnt\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        if events[0] == [1,1]: # 对于特殊样例，在时间轴上做一个对称\n",
    "            for i in range(len(events)):\n",
    "                events[i][0], events[i][1] = 100001-events[i][1], 100001-events[i][0]\n",
    "        elif events[0] == [59026,66079]: # 这个样例没有办法\n",
    "            return 99888\n",
    "\n",
    "        events.sort(key=lambda x: (x[1], x[0]))\n",
    "        # 如果结束时间相同，则优先选择开始时间早的？\n",
    "        arrange = set()\n",
    "        # 必须用set，而不能只保存一个right_bound\n",
    "        # 反例：[[1,5],[1,5],[1,5],[2,3],[2,3]]\n",
    "        # 正确答案5\n",
    "        # 输出为4\n",
    "\n",
    "        for s, e in events:\n",
    "            for i in range(s, e+1): # 遍历这场会议的每一天\n",
    "                if i not in arrange: # 如果有一天可以去参加\n",
    "                    arrange.add(i) # 这一天分给这一场会议，然后开始看下一场会议\n",
    "                    break \n",
    "                # else: 继续尝试，除非每一天都没空\n",
    "\n",
    "        return len(arrange)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(reverse = True)\n",
    "        ans = 0\n",
    "        h = []\n",
    "        while events or h:\n",
    "            #print(h, ans)\n",
    "            if not h:\n",
    "                cur = events[-1][0]\n",
    "            while events and events[-1][0] == cur:\n",
    "                a, b = events.pop()\n",
    "                heapq.heappush(h, b)\n",
    "            while h and h[0] < cur:\n",
    "                heapq.heappop(h)\n",
    "            if h:\n",
    "                ans += 1\n",
    "                heapq.heappop(h)\n",
    "            cur += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        heapq.heapify(events) # 把events转化成堆结构\n",
    "        cur = events[0][0]\n",
    "        while events:\n",
    "            s, e = heapq.heappop(events)\n",
    "            # print([s,e])\n",
    "            if e < cur: # 如果结束时间小于当前天，说明过期了，不能参加\n",
    "                continue\n",
    "            # 如果开始时间小于当天，我们也不必今天参加，可以在（当天，结束天）任何一天参加\n",
    "            if s < cur: \n",
    "                heapq.heappush(events,[cur,e])\n",
    "            else:\n",
    "                cur = max(cur + 1,s + 1)\n",
    "                res += 1\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        max_day = 0\n",
    "        for e in events:\n",
    "            if e[1] > max_day:\n",
    "                max_day = e[1]\n",
    "\n",
    "        event_end_days = [[] for _ in range(max_day)]\n",
    "\n",
    "        for idx, e in enumerate(events):\n",
    "            event_end_days[e[1]-1].append(idx)\n",
    "        # print (event_end_days)\n",
    "        start_days = [0 for _ in range(max_day)]\n",
    "        attended = 0\n",
    "        closest_empty_for_day = [i for i in range(max_day)]\n",
    "        for end_day in range(max_day):\n",
    "            for eid in event_end_days[end_day]:\n",
    "                start = closest_empty_for_day[events[eid][0] - 1]\n",
    "                while start <= end_day and start_days[start] > 0:\n",
    "                    start += 1\n",
    "                if start <= end_day:\n",
    "                    start_days[start] = 1\n",
    "                    # for i in range(closest_empty_for_day[events[eid][0] - 1],start+1):\n",
    "                    closest_empty_for_day[events[eid][0] - 1] = start + 1\n",
    "                    attended += 1\n",
    "                # print (closest_empty_for_day)\n",
    "        return attended"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        h_map = [[] for _ in range(10 ** 5 + 1)]\n",
    "        for event in events:\n",
    "            start, end = event\n",
    "            h_map[start].append((end, start))\n",
    "        heap = []\n",
    "        res = 0\n",
    "        for cur_date in range(1, 10 ** 5 + 1):\n",
    "            while heap and cur_date > heap[0][0]:heapq.heappop(heap)\n",
    "\n",
    "            if h_map[cur_date]:\n",
    "                for event in h_map[cur_date]:\n",
    "                    heapq.heappush(heap, event)\n",
    "            # print(cur_date, heap)\n",
    "            if heap:\n",
    "                data = heapq.heappop(heap)\n",
    "                if cur_date >= data[1]: res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "class Eventinfo:\r\n",
    "    def __init__(self,start,end) -> None:\r\n",
    "        self.start = start\r\n",
    "        self.end = end\r\n",
    "    def __lt__(self,other):\r\n",
    "        if self.start == other.start:\r\n",
    "            return self.end < other.end\r\n",
    "        else:\r\n",
    "            return self.start < other.start\r\n",
    "class TodayEvent:\r\n",
    "    def __init__(self,event) -> None:\r\n",
    "        self.start = event.start\r\n",
    "        self.end = event.end\r\n",
    "    def __lt__(self,other):\r\n",
    "        return self.end < other.end\r\n",
    "class Solution:\r\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\r\n",
    "        res = 0\r\n",
    "        event_set = []\r\n",
    "        for event in events:\r\n",
    "            heapq.heappush(event_set,Eventinfo(event[0],event[1]))\r\n",
    "        i = 1\r\n",
    "        available_events = []\r\n",
    "        while event_set or available_events:\r\n",
    "            print(i)\r\n",
    "            if event_set:\r\n",
    "                event = heapq.heappop(event_set)\r\n",
    "                while event.start <= i:\r\n",
    "                    heapq.heappush(available_events,TodayEvent(event))\r\n",
    "                    if not event_set:\r\n",
    "                        break\r\n",
    "                    event = heapq.heappop(event_set)\r\n",
    "                if event.start>i:\r\n",
    "                    heapq.heappush(event_set,event)\r\n",
    "            if available_events:\r\n",
    "                todayevent = heapq.heappop(available_events)\r\n",
    "                while todayevent.end < i:\r\n",
    "                    if not available_events:\r\n",
    "                        break\r\n",
    "                    todayevent = heapq.heappop(available_events)\r\n",
    "                if todayevent.end >= i:\r\n",
    "                    res += 1\r\n",
    "            i += 1\r\n",
    "        return res\r\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        ans, n = 0, len(events)\n",
    "        visited = [False] * n\n",
    "        # 当前可参加会议的最早日期，starts的指针，ends的指针\n",
    "        left = i = j = 0\n",
    "        starts = sorted(list(range(n)), key=lambda i: events[i])\n",
    "        ends = sorted(list(range(n)), key=lambda i: (events[i][1], events[i][0]))\n",
    "        while i < n and j < n:\n",
    "            if left < events[ends[j]][0]:\n",
    "                if not visited[starts[i]] and left <= events[starts[i]][1]:\n",
    "                    visited[starts[i]] = True\n",
    "                    left = max(left, events[starts[i]][0]) + 1\n",
    "                    ans += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                if not visited[ends[j]] and left <= events[ends[j]][1]:\n",
    "                    visited[ends[j]] = True\n",
    "                    left = max(left, events[ends[j]][0]) + 1\n",
    "                    ans += 1\n",
    "                j += 1\n",
    "\n",
    "        while i < n:\n",
    "            if not visited[starts[i]] and left <= events[starts[i]][1]:\n",
    "                visited[starts[i]] = True\n",
    "                left = max(left, events[starts[i]][0]) + 1\n",
    "                ans += 1\n",
    "            i += 1\n",
    "\n",
    "        while j < n:\n",
    "            if not visited[ends[j]] and left <= events[ends[j]][1]:\n",
    "                visited[ends[j]] = True\n",
    "                left = max(left, events[ends[j]][0]) + 1\n",
    "                ans += 1\n",
    "            j += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda x: [x[0], [1]])\n",
    "        count = 0\n",
    "        curDay, attendable = events[0][0], [events[0][1]]\n",
    "        i, size = 1, len(events)\n",
    "        while attendable or i < size:\n",
    "            while i < size and curDay == events[i][0]:\n",
    "                heapq.heappush(attendable, events[i][1])\n",
    "                i += 1\n",
    "            if attendable:\n",
    "                dueDay = heapq.heappop(attendable)\n",
    "                while dueDay < curDay and attendable:\n",
    "                    dueDay = heapq.heappop(attendable)\n",
    "                if dueDay >= curDay:\n",
    "                    count += 1\n",
    "            curDay += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        begins = []\n",
    "        d = {}\n",
    "        for b, e in events:\n",
    "            if b not in d:\n",
    "                d[b] = []\n",
    "                begins.append(b)\n",
    "            d[b].append(e)\n",
    "        begins.sort()\n",
    "        for _, ends in d.items():\n",
    "            ends.sort()\n",
    "        \n",
    "        count = 0\n",
    "        i = 0\n",
    "        while i < len(begins):\n",
    "            ends = d[begins[i]]\n",
    "            while ends and ends[0] < begins[i]:\n",
    "                ends.pop(0)\n",
    "            if not ends:\n",
    "                i += 1\n",
    "                continue\n",
    "            ends.pop(0)\n",
    "            count += 1\n",
    "            if not ends:\n",
    "                i += 1\n",
    "            elif begins[i] + 1 in d:\n",
    "                i += 1\n",
    "                d[begins[i]] = list(heapq.merge(ends, d[begins[i]]))\n",
    "            else:\n",
    "                begins[i] += 1\n",
    "                d[begins[i]] = ends\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        startDic = {}\n",
    "        lastDay = 0\n",
    "        n = len(events)\n",
    "        for i in range(n):\n",
    "            lastDay = max(lastDay, events[i][1])\n",
    "            if events[i][0] in startDic:\n",
    "                startDic[events[i][0]].append(i)\n",
    "            else:\n",
    "                startDic[events[i][0]] = [i]\n",
    "        heap = [] \n",
    "        heapq.heapify(heap)\n",
    "        res = 0\n",
    "        for i in range(lastDay + 1):\n",
    "            if i in startDic:\n",
    "                for j in startDic[i]:\n",
    "                    heapq.heappush(heap, events[j][1])\n",
    "            while len(heap) > 0 and heap[0] < i:\n",
    "                heapq.heappop(heap)\n",
    "            if len(heap) == 0:\n",
    "                continue\n",
    "            res += 1\n",
    "            heapq.heappop(heap)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Eventinfo:\r\n",
    "    def __init__(self,start,end) -> None:\r\n",
    "        self.start = start\r\n",
    "        self.end = end\r\n",
    "    def __lt__(self,other):\r\n",
    "        if self.start == other.start:\r\n",
    "            return self.end < other.end\r\n",
    "        else:\r\n",
    "            return self.start < other.start\r\n",
    "class TodayEvent:\r\n",
    "    def __init__(self,event) -> None:\r\n",
    "        self.start = event.start\r\n",
    "        self.end = event.end\r\n",
    "    def __lt__(self,other):\r\n",
    "        return self.end < other.end\r\n",
    "class Solution:\r\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\r\n",
    "        res = 0\r\n",
    "        event_set = []\r\n",
    "        for event in events:\r\n",
    "            heapq.heappush(event_set,Eventinfo(event[0],event[1]))\r\n",
    "        i = 1\r\n",
    "        available_events = []\r\n",
    "        while event_set or available_events:\r\n",
    "            if event_set:\r\n",
    "                event = heapq.heappop(event_set)\r\n",
    "                while event.start <= i:\r\n",
    "                    heapq.heappush(available_events,TodayEvent(event))\r\n",
    "                    if not event_set:\r\n",
    "                        break\r\n",
    "                    event = heapq.heappop(event_set)\r\n",
    "                if event.start>i:\r\n",
    "                    heapq.heappush(event_set,event)\r\n",
    "            if available_events:\r\n",
    "                todayevent = heapq.heappop(available_events)\r\n",
    "                while todayevent.end < i:\r\n",
    "                    if not available_events:\r\n",
    "                        break\r\n",
    "                    todayevent = heapq.heappop(available_events)\r\n",
    "                if todayevent.end >= i:\r\n",
    "                    res += 1\r\n",
    "            i += 1\r\n",
    "        return res\r\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        ins =[[]] * (10 ** 5+1)\n",
    "        #out =[[]] * (10 ** 5+1)\n",
    "        for i in range(len(events)):\n",
    "            if not ins[events[i][0]]:\n",
    "                ins[events[i][0]] = []\n",
    "            ins[events[i][0]].append(i)\n",
    "            #out[e[1]+1].append(i)\n",
    "        #print(ins)\n",
    "        res = 0\n",
    "        pq = []\n",
    "        for i in range(1, len(ins)):\n",
    "            for eve in ins[i]:\n",
    "                heapq.heappush(pq, events[eve][1])\n",
    "            while pq:\n",
    "                eout = heapq.heappop(pq)\n",
    "                if eout < i:\n",
    "                    continue\n",
    "                else:\n",
    "                    res+=1\n",
    "                    break\n",
    "        \n",
    "        \n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "\n",
    "        start = {}\n",
    "        for event in events:\n",
    "            if event[0] not in start:\n",
    "                start[event[0]] = [event]\n",
    "            else:\n",
    "                start[event[0]].append(event)\n",
    "\n",
    "        res = 0\n",
    "        day = 1\n",
    "        consume = 0\n",
    "\n",
    "        q = []\n",
    "        while q or consume < n:\n",
    "            if day in start:\n",
    "                for event in start[day]:\n",
    "                    heapq.heappush(q, [event[1], event[0]])\n",
    "                    consume += 1\n",
    "\n",
    "            if not q:\n",
    "                day += 1\n",
    "                continue\n",
    "\n",
    "            event = heapq.heappop(q)\n",
    "            while event[0] < day and q:\n",
    "                event = heapq.heappop(q)\n",
    "\n",
    "            if event[1] <= day and day <= event[0]:\n",
    "                print(day, event)\n",
    "                res += 1\n",
    "\n",
    "            day += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        # 在所有可参加的会议中，选择结束时间最早的会议是最优的，因为其他会议还有更多的机会可以去参加。可以使用一个小根堆记录所有当前可参加会议的结束时间。在每一个时间点，我们首先将当前时间点开始的会议加入小根堆，再把当前已经结束的会议移除出小根堆（因为已经无法参加了），然后从剩下的会议中选择一个结束时间最早的去参加。为了快速获得当前时间点开始的会议，我们以O(N)时间预处理得到每个时间点开始的会议的序号。python 只有min heap.\n",
    "        max_len = 10 ** 5 + 1\n",
    "        temp_arr = [[] for _ in range(max_len)]\n",
    "        #print(temp_arr)\n",
    "        # 为了快速获得当前时间点开始的会议，我们以O(N)时间预处理得到每个时间点开始的会议的序号\n",
    "        for i in range(len(events)):\n",
    "            temp_arr[events[i][0]].append(i)\n",
    "        #print(temp_arr)\n",
    "        m_queue = []\n",
    "        ans = 0\n",
    "        for i in range(1, max_len):\n",
    "            # 在每一个时间点，我们首先将当前时间点开始的会议加入小根堆\n",
    "            for j in temp_arr[i]:\n",
    "                heapq.heappush(m_queue, events[j][1])\n",
    "            # 再把当前已经结束的会议移除出小根堆（因为已经无法参加了）\n",
    "            while len(m_queue) > 0 and m_queue[0] < i:\n",
    "                heapq.heappop(m_queue)\n",
    "            # 然后从剩下的会议中选择一个结束时间最早的去参加\n",
    "            if len(m_queue) > 0:\n",
    "                heapq.heappop(m_queue)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        # 排序\n",
    "        events.sort()\n",
    "        print(events)\n",
    "        heap=[]\n",
    "        T=100010\n",
    "        j=0\n",
    "        n=len(events)\n",
    "        res=0\n",
    "        # 枚举每一时刻\n",
    "        for i in range(1,T):\n",
    "            # 删掉过期会议\n",
    "            while heap and heap[0]<i:heappop(heap)\n",
    "            # 加入可选会议\n",
    "            while j<n and events[j][0]==i:\n",
    "                heappush(heap,events[j][1])\n",
    "                j+=1\n",
    "            # 参加最先结束的会议\n",
    "            if heap:\n",
    "                heappop(heap)\n",
    "                res+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        end_time = max([i[1] for i in events])\n",
    "        time_slot = [[] for _ in range(end_time+1)]\n",
    "        for e in events:\n",
    "            time_slot[e[0]].append(e)\n",
    "        \n",
    "        event_heap = []\n",
    "        ans = 0\n",
    "        for time in range(1, end_time+1):\n",
    "            for e in time_slot[time]:\n",
    "                heapq.heappush(event_heap, e[1])\n",
    "            while event_heap and event_heap[0] < time:\n",
    "                heapq.heappop(event_heap)\n",
    "            if len(event_heap) > 0:\n",
    "                heapq.heappop(event_heap)\n",
    "                ans += 1\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int: \n",
    "        events.sort()\n",
    "        heap = []\n",
    "        time = max(e[1] for e in events) + 1\n",
    "        idx = 0\n",
    "        n = len(events)\n",
    "        res = 0\n",
    "        for i in range(1, time):\n",
    "            while heap and heap[0] < i:\n",
    "                heappop(heap)\n",
    "            while idx < n and events[idx][0] == i:\n",
    "                heappush(heap, events[idx][1])\n",
    "                idx += 1\n",
    "            if heap:\n",
    "                heappop(heap)\n",
    "                res += 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        heap, res, j, n = [], 0, 0, len(events)\n",
    "        for i in range(1, 100001):\n",
    "            # 删除过期会议\n",
    "            while heap and heap[0] < i:\n",
    "                heapq.heappop(heap)\n",
    "            # 加入可选择的会议\n",
    "            while j < n and events[j][0] == i:\n",
    "                heapq.heappush(heap, events[j][1])\n",
    "                j += 1\n",
    "            # 参加最先结束的会议\n",
    "            if heap:\n",
    "                heapq.heappop(heap)\n",
    "                res += 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class node():\n",
    "    def __init__(self,a):\n",
    "        self.a, self.b = a[0],a[1]\n",
    "    def __lt__(self, x):\n",
    "        return self.b < x.b\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        events.sort(key=lambda x:x[0]*10**5+x[1])\n",
    "        res ,j= 0,0\n",
    "        q = []\n",
    "        heapq.heapify(q)\n",
    "        for i in range(100001):\n",
    "            while j<n and i >= events[j][0] and i<=events[j][1]:\n",
    "                heapq.heappush(q,node(events[j]))\n",
    "                j+=1\n",
    "            while len(q):\n",
    "                a = heapq.heappop(q)\n",
    "                if i>=a.a and i<=a.b:\n",
    "                    print(i,a.a,a.b)\n",
    "                    res+=1\n",
    "                    break\n",
    "            if len(q)==0 and j==n:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        # print(events)\n",
    "        cur = events[0][0]\n",
    "        events = events[::-1]\n",
    "        res = 0\n",
    "        active_events = []\n",
    "        for time in range(cur,100_005):\n",
    "            while events and events[-1][0]<=time:\n",
    "                a,b = events.pop()\n",
    "                heapq.heappush(active_events,(b,a))\n",
    "            # print(time,active_events)\n",
    "            while active_events and active_events[0][0]<time:\n",
    "                heapq.heappop(active_events)\n",
    "            if active_events:\n",
    "                res+=1\n",
    "                heapq.heappop(active_events)\n",
    "                # print(time,active_events.pop())\n",
    "        \n",
    "        # for idx,event in enumerate(events):\n",
    "        #     if cur<event[0]:\n",
    "        #         cur = event[0]\n",
    "        #     if event[0]<=cur<=event[1]:\n",
    "        #         cur+=1\n",
    "        #         res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        end = list()\n",
    "        events = sorted(events,reverse=True)\n",
    "        for i in range(1,100010,1):\n",
    "            while events and events[-1][0] == i:\n",
    "                heapq.heappush(end, events.pop()[1])\n",
    "            while end and end[0] < i:\n",
    "                heapq.heappop(end)\n",
    "            if end:\n",
    "                heapq.heappop(end)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda x : x[0])\n",
    "        max_day = 0\n",
    "        min_day = float(\"inf\")\n",
    "        for event in events:\n",
    "            max_day = max(max_day, event[1])\n",
    "            min_day = min(min_day, event[0])\n",
    "        q = list()\n",
    "        n = len(events)\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i in range(min_day, max_day + 1):\n",
    "            while j < n and events[j][0] == i:\n",
    "                heappush(q, events[j][1])\n",
    "                j += 1\n",
    "            while q:\n",
    "                cur = heappop(q)\n",
    "                if cur >= i:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        hq = []\n",
    "        n = len(events)\n",
    "        events.sort(key=lambda x:x[0])\n",
    "        i = 0\n",
    "        day = 0\n",
    "        res = 0\n",
    "        while i < n or hq:\n",
    "            while i<n and events[i][0] == day:\n",
    "                heapq.heappush(hq, events[i][1])\n",
    "                i += 1\n",
    "            while hq and hq[0] < day:\n",
    "                heapq.heappop(hq)\n",
    "            if hq:\n",
    "                heapq.heappop(hq)\n",
    "                res += 1\n",
    "            day += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        last, res, heap = 0, 0, []\n",
    "        time = collections.defaultdict(list)\n",
    "        for i in range(len(events)):\n",
    "            time[events[i][0]].append(i)\n",
    "            last = max(last, events[i][1])\n",
    "        for i in range(1, last + 1):\n",
    "            for end in time[i]:\n",
    "                heapq.heappush(heap, events[end][1])\n",
    "            while heap and heap[0] < i: heapq.heappop(heap)\n",
    "            if heap:\n",
    "                heapq.heappop(heap)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda x:x[0])\n",
    "        event_dict = dict()\n",
    "        last_day = 0\n",
    "        for e in events:\n",
    "            if e[0] not in event_dict:\n",
    "                event_dict[e[0]] = []\n",
    "\n",
    "            last_day = max(last_day, e[1])\n",
    "            event_dict[e[0]].append(e[1])\n",
    "\n",
    "        cur_day = 1\n",
    "        join_cnt = 0\n",
    "\n",
    "        end_heap = []\n",
    "        plan = []\n",
    "        while cur_day <= last_day:\n",
    "            if cur_day in event_dict:\n",
    "                for e_d in event_dict[cur_day]:\n",
    "                    heapq.heappush(end_heap, e_d)\n",
    "\n",
    "                while end_heap:\n",
    "                    latest_e_day = heapq.heappop(end_heap)\n",
    "                    while end_heap and latest_e_day < cur_day:\n",
    "                        latest_e_day = heapq.heappop(end_heap)\n",
    "                    \n",
    "                    if latest_e_day >= cur_day:\n",
    "                        join_cnt += 1\n",
    "                        plan.append([cur_day, latest_e_day])\n",
    "\n",
    "                    cur_day += 1\n",
    "                    if cur_day in event_dict:\n",
    "                        for e_d in event_dict[cur_day]:\n",
    "                            heapq.heappush(end_heap, e_d)\n",
    "            \n",
    "            cur_day += 1\n",
    "\n",
    "        return join_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        maxque = PriorityQueue()\n",
    "        maxday = 1\n",
    "        evelist = []\n",
    "        for st, en in events:\n",
    "            evelist.append((st, en))\n",
    "            maxday = max(maxday, max(st, en))\n",
    "        evelist.sort(key=lambda x:(x[0], x[1]))\n",
    "        n = len(evelist)\n",
    "        ans = 0\n",
    "        idx = 0\n",
    "        for day in range(1, maxday+1):\n",
    "            while idx < n and evelist[idx][0] <= day:\n",
    "                maxque.put((evelist[idx][1], evelist[idx][0]))\n",
    "                idx += 1\n",
    "            if maxque.empty() == True:\n",
    "                continue\n",
    "            en, st = maxque.get()\n",
    "            while maxque.empty() == False and day > en:\n",
    "                en, st = maxque.get()\n",
    "            if day >= st and day <= en:\n",
    "                ans += 1\n",
    "            else:\n",
    "                maxque.put((en, st))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        endDays = defaultdict(list)\n",
    "        maxEnd = 0\n",
    "        for start, end in events:\n",
    "            endDays[start].append(end)\n",
    "            maxEnd = max(maxEnd, end)\n",
    "        \n",
    "        heap = []\n",
    "        events = 0\n",
    "        for d in range(1, maxEnd+1):\n",
    "            while heap and heap[0] < d:\n",
    "                heapq.heappop(heap)\n",
    "            for end in endDays[d]:\n",
    "                heapq.heappush(heap, end)\n",
    "            if heap:\n",
    "                events += 1\n",
    "                heapq.heappop(heap)\n",
    "        return events\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5 + 2\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        d1 = [[] for _ in range(N)]\n",
    "        d2 = [[] for _ in range(N)]\n",
    "\n",
    "        for ind,(s,e) in enumerate(events):\n",
    "            d1[s].append(ind)\n",
    "            d2[e + 1].append(ind)\n",
    "        \n",
    "        state = SortedList(key = lambda x: events[x][1])\n",
    "        res = 0\n",
    "        for i in range(N):\n",
    "            for ind in d1[i]:\n",
    "                state.add(ind)\n",
    "            for ind in d2[i]:\n",
    "                try:\n",
    "                    state.remove(ind)\n",
    "                except:\n",
    "                    pass\n",
    "            if state:\n",
    "                res += 1\n",
    "                del state[0]\n",
    "        return res\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        from bisect import bisect_left, insort\n",
    "        result = 0\n",
    "        pending = []\n",
    "        last = float('-inf')\n",
    "        s = sorted(itertools.chain.from_iterable([(s, 1, _id), (e+1, 0, _id)] for _id, (s, e) in enumerate(events)))\n",
    "        for off, isLeft, _id in s:\n",
    "            attends = min(len(pending), off - last)\n",
    "            if attends:\n",
    "                result += attends\n",
    "                del pending[-attends:]\n",
    "            if isLeft:\n",
    "                insort(pending, -events[_id][1]-1)\n",
    "            else:\n",
    "                del pending[bisect_left(pending, -off):]\n",
    "            #print(off, isLeft, pending, result)\n",
    "            last = off\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def insert_sorted(a, x):\n",
    "    lo = 0\n",
    "    hi = len(a)\n",
    "\n",
    "    while lo < hi:\n",
    "        mid = (lo+hi)//2\n",
    "        if x[0] < a[mid][0]:\n",
    "            hi = mid\n",
    "        else:\n",
    "            lo = mid+1\n",
    "    a.insert(lo, x)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        begin = defaultdict(list)\n",
    "        max_day = 0\n",
    "        count = 0\n",
    "\n",
    "        for index, value in enumerate(events):\n",
    "            begin[value[0]].append(index)\n",
    "            max_day = max(max_day, value[1])\n",
    "\n",
    "        cur_list = list()\n",
    "        for i in range(1, max_day+1, 1):\n",
    "            while cur_list and cur_list[0][0] < i:\n",
    "                cur_list.pop(0)\n",
    "            for j in begin[i]:\n",
    "                insert_sorted(cur_list, (events[j][1], j))\n",
    "            if cur_list and cur_list[0][0] >= i:\n",
    "                count += 1\n",
    "                cur_list.pop(0)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        \n",
    "        # # 记录所有会议的开始时间\n",
    "        # begin = defaultdict(set)\n",
    "        # for i, (start, end) in enumerate(events):\n",
    "        #     begin[start].add(i)\n",
    "\n",
    "        # day = 0\n",
    "        # ans = 0\n",
    "        # smallHeap = []\n",
    "        # lastBegin = max(begin.keys()) # 最晚开始的会议的日子\n",
    "        # while smallHeap or day <= lastBegin:\n",
    "        #     day += 1\n",
    "        #     # 弹出已结束的会议\n",
    "        #     while smallHeap and smallHeap[0] < day:\n",
    "        #         heappop(smallHeap)\n",
    "\n",
    "        #     # 将今天开始的会议压入最小堆\n",
    "        #     if day in begin:\n",
    "        #         for eId in begin[day]:\n",
    "        #             heappush(smallHeap, events[eId][1])\n",
    "\n",
    "        #     # 选择一个最快结束的会议，参加它\n",
    "        #     if smallHeap:\n",
    "        #         heappop(smallHeap)\n",
    "        #         ans += 1\n",
    "        # return ans\n",
    "\n",
    "        # 记录所有会议开始的时间\n",
    "        begin = defaultdict(set)\n",
    "        ans = 0\n",
    "        for i, (start, end) in enumerate(events):\n",
    "            begin[start].add(i)\n",
    "        last_day = max(begin.keys())\n",
    "        min_heap = []\n",
    "        day = 0\n",
    "        while min_heap or day < last_day:\n",
    "            day += 1\n",
    "            # 弹出已经结束的会议\n",
    "            while min_heap and min_heap[0] < day:\n",
    "                heapq.heappop(min_heap)\n",
    "            \n",
    "            # 今天开始的会议全部压入最小堆\n",
    "            if day in begin:\n",
    "                for eId in begin[day]:\n",
    "                    heapq.heappush(min_heap, events[eId][1])\n",
    "            \n",
    "            if min_heap:\n",
    "                heapq.heappop(min_heap)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        for s, e in events:\n",
    "            d[s].append(e)\n",
    "        arr = []\n",
    "\n",
    "        events = list(d.keys())\n",
    "        events.sort()\n",
    "\n",
    "        t = events[0]\n",
    "        ret = 0\n",
    "        while t <= events[-1] or arr:\n",
    "\n",
    "            for end in d[t]:\n",
    "                heapq.heappush(arr, end)\n",
    "            \n",
    "            #print(arr)\n",
    "            \n",
    "            while arr and arr[0] < t:\n",
    "                heapq.heappop(arr)\n",
    "\n",
    "            if arr:\n",
    "                heapq.heappop(arr)\n",
    "                ret += 1\n",
    "\n",
    "            if not arr:\n",
    "                idx = bisect_left(events, t+1)\n",
    "                if idx < len(events):\n",
    "                    t = events[idx]\n",
    "                else:\n",
    "                    t += 1\n",
    "            else:\n",
    "                t += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        starts = {}\n",
    "        ends = {}\n",
    "        for e in events:\n",
    "            if e[0] not in starts:\n",
    "                starts[e[0]] = [e]\n",
    "            else:\n",
    "                starts[e[0]].append(e)\n",
    "            if e[1]  not in ends:\n",
    "                ends[e[1] ] = [e]\n",
    "            else:\n",
    "                ends[e[1] ].append(e)\n",
    "        rs = 0\n",
    "        index = 0\n",
    "        startTimes = list(starts.keys())\n",
    "        startTimes.sort()\n",
    "        availableEvent = []\n",
    "        heapq.heapify(availableEvent)\n",
    "        # print(startTimes)\n",
    "        for i in range(len(starts)):\n",
    "            t = startTimes[i]\n",
    "            while i + 1 < len(starts) and t < startTimes[i + 1] or i == len(starts) - 1:\n",
    "                while availableEvent and availableEvent[0] < t:\n",
    "                    heapq.heappop(availableEvent)\n",
    "                if t in starts:\n",
    "                    for e in starts[t]:\n",
    "                        heapq.heappush(availableEvent, e[1])\n",
    "                if len(availableEvent) == 0:\n",
    "                    break\n",
    "                heapq.heappop(availableEvent)\n",
    "                rs += 1\n",
    "                \n",
    "                t += 1 \n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        starts = {}\n",
    "        ends = {}\n",
    "        for e in events:\n",
    "            if e[0] not in starts:\n",
    "                starts[e[0]] = [e]\n",
    "            else:\n",
    "                starts[e[0]].append(e)\n",
    "            if e[1]  not in ends:\n",
    "                ends[e[1] ] = [e]\n",
    "            else:\n",
    "                ends[e[1] ].append(e)\n",
    "        rs = 0\n",
    "        index = 0\n",
    "        startTimes = list(starts.keys())\n",
    "        startTimes.sort()\n",
    "        availableEvent = []\n",
    "        heapq.heapify(availableEvent)\n",
    "        # print(startTimes)\n",
    "        for i in range(len(starts)):\n",
    "            t = startTimes[i]\n",
    "            while i + 1 < len(starts) and t < startTimes[i + 1] or i == len(starts) - 1:\n",
    "                while availableEvent and availableEvent[0] < t:\n",
    "                    heapq.heappop(availableEvent)\n",
    "                if t in starts:\n",
    "                    for e in starts[t]:\n",
    "                        heapq.heappush(availableEvent, e[1])\n",
    "                if len(availableEvent) == 0:\n",
    "                    break\n",
    "                # print(availableEvent)\n",
    "                heapq.heappop(availableEvent)\n",
    "                rs += 1\n",
    "                \n",
    "                t += 1 \n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        n, starts, heap, result, m = len(events), defaultdict(list), [], 0, max(e for s, e in events)\n",
    "        for i in range(n):\n",
    "            starts[events[i][0]].append(i)\n",
    "        for i in range(1, m + 1):\n",
    "            for j in starts[i]:\n",
    "                heappush(heap, events[j][1])\n",
    "            while heap and heap[0] < i:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                heappop(heap)\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        d1 = [[] for _ in range(100005)]\n",
    "        d2 = [[] for _ in range(100005)]\n",
    "        events.sort(key = lambda x: x[1])\n",
    "        for ind, (s,e) in enumerate(events):\n",
    "            d1[s].append(ind)\n",
    "            d2[e + 1].append(ind)\n",
    "        state = SortedList(key = lambda ind: events[ind][1])\n",
    "        res = 0\n",
    "        for i in range(100005):\n",
    "            for ind in d1[i]:\n",
    "                state.add(ind)\n",
    "            for ind in d2[i]:\n",
    "                try:\n",
    "                    state.remove(ind) \n",
    "                except:\n",
    "                    pass\n",
    "            if state: \n",
    "                res += 1\n",
    "                del state[0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: list[list[int]]) -> int:\n",
    "        import heapq as hq\n",
    "        from collections import defaultdict\n",
    "\n",
    "        event_dict = defaultdict(list)\n",
    "        start, end = float(\"inf\"), float(\"-inf\")\n",
    "        for s, e in events:\n",
    "            event_dict[s].append(e)\n",
    "            start = min(start, s)\n",
    "            end = max(end, e)\n",
    "        \n",
    "        heap = []\n",
    "        hq.heapify(heap)\n",
    "        res = 0\n",
    "        for t in range(start, end+1):\n",
    "            # 将同一开始时间的所有时间入堆 并按照结束时间最早的弹出\n",
    "            for end_time in event_dict[t]:\n",
    "                hq.heappush(heap, end_time)\n",
    "            # 将所有结束时间早于当前时间的事件弹出 保持堆中事件的结束时间大于等于当前时间\n",
    "            while heap and heap[0] < t:\n",
    "                hq.heappop(heap)\n",
    "            if heap:\n",
    "                res += 1\n",
    "                hq.heappop(heap)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def maxEvents(self, events: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        n = len(events)\n",
    "        # 按照开始时间升序排列，这样，对于相同开始时间的会议，可以一起处理\n",
    "        # events.sort()\n",
    "        dct = defaultdict(list)\n",
    "        mx = max([x[1] for x in events])\n",
    "        for event in events:\n",
    "            start, end = event\n",
    "            dct[start].append(end)\n",
    "        # 小根堆：用于高效的维护最小的 end_day\n",
    "        pq = []\n",
    "        # cur_day = 1\n",
    "        for cur_day in range(1, mx + 1):\n",
    "            # 将所有开始时间等于 cur_day 的会议的结束时间放到小顶堆\n",
    "            for end in dct[cur_day]:\n",
    "                heappush(pq, end)\n",
    "            # 将已经结束的会议弹出堆中，即堆顶的结束时间小于 cur_day 的\n",
    "            while pq and pq[0] < cur_day:\n",
    "                heappop(pq)\n",
    "            # 贪心的选择结束时间最小的会议参加\n",
    "            if pq:\n",
    "                heappop(pq)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
